#include <iostream>
#include <vector>
#include "lib/list.h"
using namespace std;

ListNode* mergeSortedListIterative(ListNode* head1, ListNode* head2) {
  if (head1 == nullptr) return head2;
  if (head2 == nullptr) return head1;
  auto node1 = head1;
  auto node2 = head2;
  ListNode* ret_node;
  if (head1->value < head2->value) {
    ret_node = head1;
    node1 = node1->next;
  } else {
    ret_node = head2;
    node2 = node2->next;
  }
  auto cur_node = ret_node;
  while (node1 && node2) {
    if (node1->value < node2->value) {
      cur_node->next = node1;
      node1 = node1->next;
      cur_node = cur_node->next;
    } else {
      cur_node->next = node2;
      node2 = node2->next;
      cur_node = cur_node->next;
    }
  }
  if (node1) cur_node->next = node1;
  if (node2) cur_node->next = node2;
  return ret_node;
}

ListNode* mergeSortedListRecursive(ListNode* head1, ListNode* head2) {
  if (head1 == nullptr) return head2;
  if (head2 == nullptr) return head1;
  ListNode* merged_head = nullptr;
  if (head1->value < head2->value) {
    merged_head = head1;
    merged_head->next = mergeSortedListRecursive(head1->next, head2);
  } else {
    merged_head = head2;
    merged_head->next = mergeSortedListRecursive(head1, head2->next);
  }
  return merged_head;
}

int main() {
  vector<int> vec1 = {1, 3, 5, 7, 9, 13, 16};
  vector<int> vec2 = {2, 4, 6, 8, 10, 11, 12, 13, 14, 15};
  ListNode* head1 = CreateList(vec1);
  ListNode* head2 = CreateList(vec2);
  ListNode* merged_head_iterative = mergeSortedListIterative(head1, head2);
  PrintList(merged_head_iterative);

  ListNode* head3 = CreateList(vec1);
  ListNode* head4 = CreateList(vec2);
  ListNode* merged_head_recursive = mergeSortedListRecursive(head3, head4);
  PrintList(merged_head_recursive);

  DeleteList(merged_head_iterative);
  DeleteList(merged_head_recursive);

  return 0;
}
